package com.yoshino.leetcode.improve40.twentyfirst;

import java.util.List;

class Solution {
    class WordTree {
        String word;
        WordTree[] next;
        public WordTree() {
            next = new WordTree[26];
        }
    }
    private void add(String word) {
        WordTree cur = root;
        for (char c : word.toCharArray()) {
            if (cur.next[c - 'a'] == null) {
                cur.next[c - 'a'] = new WordTree();
            }
            cur = cur.next[c - 'a'];
        }
        // 结尾
        cur.word = word;
    }

    private String get(String word) {
        WordTree cur = root;
        for (char c : word.toCharArray()) {
            if (cur.next[c - 'a'] == null) {
                return null;
            }
            cur = cur.next[c - 'a'];
            // 优先最短前缀
            if (cur.word != null) {
                break;
            }
        }
        // 是否为结尾
        return cur.word;
    }

    // 根结点
    WordTree root;
    public String replaceWords(List<String> dictionary, String sentence) {
        // 使用前缀树匹配，不过将 isEnd 替换为 对应的 word
        // 因为需要替换，不然得回溯或额外记录长度
        root = new WordTree();
        // 填充前缀树
        dictionary.forEach(this::add);
        String[] split = sentence.split(" ");
        for (int i = 0; i < split.length; i++) {
            String s = get(split[i]);
            if (s != null) {
                split[i] = s;
            }
        }
        return String.join(" ", split);
    }
}